i=1∑nj=i+1∑nlcm(Ai,Aj)
2∑i=1n∑j=1nlcm(Ai,Aj)−∑i=1nAi
所以只需要快速求到 ∑i=1n∑j=1nlcm(Ai,Aj) 即可 , 其实就是 P3911。
下面给一下过程:
令 ci 表示 i 出现的次数,n 为最大数字。
i=1∑nj=1∑nci×cj×lcm(i,j)
i=1∑nj=1∑nci×cj×gcd(i,j)i×j
k=1∑ni=1∑nj=1∑n[gcd(i,j)=k]ci×cj×ki×j
k=1∑ni=1∑⌊kn⌋j=1∑⌊kn⌋[gcd(i,j)=1]cik×cjk×i×j×k
k=1∑ni=1∑⌊kn⌋j=1∑⌊kn⌋d∣gcd(i,j)∑μ(d)×cik×cjk×i×j×k
k=1∑nd=1∑⌊kn⌋μ(d)×d2i=1∑⌊kdn⌋j=1∑⌊kdn⌋cikd×cjkd×i×j×k
k=1∑nkd=1∑nμ(d)×d2i=1∑⌊kdn⌋j=1∑⌊kdn⌋cikd×cjkd×i×j×k
T=1∑nT(d∣T∑μ(d)×d)i=1∑⌊Tn⌋j=1∑⌊Tn⌋ciT×cjT×i×j
T=1∑nT(d∣T∑μ(d)×d)(i=1∑⌊Tn⌋ciT×i)2
第一个括号预处理,第二个括号直接暴力算。
预处理和查询复杂度均为 Θ(nlnn)。
#include <cstdio>
#include <iostream>
using namespace std;
const int MAXN = 1e6 , Mod = 998244353;
int n , m , Ans , cnt[ MAXN + 5 ];
int k , prime[ MAXN + 5 ] , mu[ MAXN + 5 ] , f[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void sieve( ) {
mu[ 1 ] = 1;
for( int i = 2 ; i <= MAXN ; i ++ ) {
if( !vis[ i ] ) {
prime[ ++ k ] = i;
mu[ i ] = -1;
}
for( int j = 1 ; j <= k && i * prime[ j ] <= MAXN ; j ++ ) {
vis[ i * prime[ j ] ] = 1;
if( i % prime[ j ] == 0 ) break;
mu[ i * prime[ j ] ] = -mu[ i ];
}
}
for( int i = 1 ; i <= MAXN ; i ++ )
for( int j = i ; j <= MAXN ; j += i )
f[ j ] = ( f[ j ] + i * mu[ i ] + Mod ) % Mod;
}
int main( ) {
sieve( );
scanf("%d",&n);
for( int i = 1 , x ; i <= n ; i ++ ) {
scanf("%d",&x) , Ans = ( Ans - x + Mod ) % Mod;
cnt[ x ] ++ , m = max( m , x );
}
n = m;
for( int i = 1 ; i <= n ; i ++ ) {
int tmp = 0;
for( int j = 1 ; j <= n / i ; j ++ )
tmp = ( tmp + 1ll * cnt[ i * j ] * j % Mod ) % Mod;
Ans = ( Ans + 1ll * i * f[ i ] % Mod * tmp % Mod * tmp % Mod ) % Mod;
}
printf("%d", 1ll * Ans * 499122177 % Mod );
return 0;
}